package leetcode.code1690;

class Solution9 {
	// 所以就是这个结构
		public static int[][][][] dp = new int[1000][1000][2][2];

		public static int stoneGameVII(int[] stones) {
			int len = stones.length;
			int[] sums = new int[len + 1];
			for (int i = 1; i < sums.length; i++) {
				sums[i] = sums[i - 1] + stones[i - 1];
			}
			// dp[a][b][c][0] = -1，表示：
			// (a,b,c)这个状态没算过
			for (int a = 0; a < len; a++) {
				for (int b = 0; b < len; b++) {
					for (int c = 0; c < 2; c++) {
						dp[a][b][c][0] = -1;
					}
				}
			}
			alice(stones, sums, 0, len - 1);
			return dp[0][len - 1][0][0] - dp[0][len - 1][0][1];
		}

		public static void alice(int[] stones, int[] sums, int l, int r) {
			if (dp[l][r][0][0] != -1) {
				return;
			}
			if (l + 1 == r) {
				if (stones[l] <= stones[r]) {
					dp[l][r][0][0] = stones[r];
					dp[l][r][0][1] = 0;
				} else {
					dp[l][r][0][0] = stones[l];
					dp[l][r][0][1] = 0;
				}
			} else {
				bob(stones, sums, l + 1, r);
				int ans10 = dp[l + 1][r][1][0] + sums[r + 1] - sums[l + 1];
				int ans11 = dp[l + 1][r][1][1];
				bob(stones, sums, l, r - 1);
				int ans20 = dp[l][r - 1][1][0] + sums[r] - sums[l];
				int ans21 = dp[l][r - 1][1][1];
				if (ans10 - ans11 >= ans20 - ans21) {
					dp[l][r][0][0] = ans10;
					dp[l][r][0][1] = ans11;
				} else {
					dp[l][r][0][0] = ans20;
					dp[l][r][0][1] = ans21;
				}
			}
		}

		public static void bob(int[] stones, int[] sums, int l, int r) {
			if (dp[l][r][1][0] != -1) {
				return;
			}
			if (l + 1 == r) {
				if (stones[l] <= stones[r]) {
					dp[l][r][1][0] = 0;
					dp[l][r][1][1] = stones[r];
				} else {
					dp[l][r][1][0] = 0;
					dp[l][r][1][1] = stones[l];
				}
			} else {
				alice(stones, sums, l + 1, r);
				int ans10 = dp[l + 1][r][0][0];
				int ans11 = dp[l + 1][r][0][1] + sums[r + 1] - sums[l + 1];
				alice(stones, sums, l, r - 1);
				int ans20 = dp[l][r - 1][0][0];
				int ans21 = dp[l][r - 1][0][1] + sums[r] - sums[l];
				if (ans10 - ans11 >= ans20 - ans21) {
					dp[l][r][1][0] = ans20;
					dp[l][r][1][1] = ans21;
				} else {
					dp[l][r][1][0] = ans10;
					dp[l][r][1][1] = ans11;
				}
			}
		}
	}